A. Organizing Retrieval Results
Increasingly, the public accesses text collections and their information electronically, identifying desired documents by submitting a search query. The standard approach for displaying search results for electronic text collections is to present, in ranked order, a list of document titles. Often shown alongside each title is a numerical score signifying the degree of match between the document and the query, or the estimated relevance of the document to the query. On-line bibliographic systems show meta-data about the documents, such as author and publisher, alongside the title. Search engines associated with the World Wide Web commonly show short summaries or excerpts from the retrieved documents, typically extracted from the first few lines. Some systems show lines extracted from the document that match terms in the query. Document titles can also be annotated with graphics that show the correspondence between the retrieved documents and the query.
Use of category taxonomies to impose organization upon retrieval results has received little attention, even though some are associated with valuable document collections. For example, the Association for Computing Machinery (ACM) has developed a hierarchy of approximately 1200 category labels and authors are required to assign multiple categories from this taxonomy to their journal articles. Indexers for major medical journals use the MeSH (Medical Subject Headings) taxonomy of over 18,000 main subject headings to annotate articles. Category taxonomies like these are arranged in a hierarchy meant to reflect the set of concepts that define the field. For this reason, those who know the relevant domain easily understand the associated categories. Categories are restricted to a fixed set and so help reduce the space of concepts by which documents can be characterized. Categories can summarize a document's contents and by virtue of being assigned to a document, or not, distinguish those concepts that are discussed at length versus those just touched in passing.
Little use has been made of category labels in conjunction with the presentation and organization of retrieved documents other than to simply list the associated categories. Simply listing categories associated with documents is inadequate in a number of situations. One such is when many documents are assigned to a particular category so that the category does not differentiate between the retrieved documents. Another such is when many categories are associated with a set of retrieved documents so that higher level commonalties among the categories are not represented. Thus, the available categories do not capture the main themes of the retrieved documents. Finally, the categories available may not be adequate because they do not characterize the information in a way that interests the user.
Yahoo's search engine for the World Wide Web provides category labels which users may use to issue search queries. These category labels are presented as an alphabetical list, with no indication of the relationship of the categories to one another, forcing users to read through them one by one. This poor presentation of the hierarchy frustrates a user when the predefined categories do not meet the user's needs. The user is forced to either navigate through irrelevant portions of the hierarchy or abandon use to the hierarchy altogether, issuing instead a search on the topic of interest.
The problems just discussed are exacerbated when documents are best characterized by multiple category labels. For example, a document whose title is "Immediate breast reconstruction after mastectomy" is not about either breast reconstruction or mastectomy alone, but about the conjunction of these topics. Each of the constitutive topics could occur without the other. There are many different ways that topics like these can combine that, for a large category set, navigating a structure containing all potential combinations is untenable.
Thus, an unfulfilled need exists for a means of using categories to specify search queries. Another unfulfilled need exists for a means of using categories to display search results when the retrieved documents are associated with category labels. This need is greater when each retrieved document is associated with many category labels.
B. The Cone Tree
A method for generating a cone tree using a computer system is described in detail in U.S. Pat. No. 5,295,243 to Robertson et al. entitled "Display of Hierarchical Three-Dimensional Structures with Rotating Substructures." Displayed on the monitor of a computer system, the cone tree is perceived by computer user as three-dimensional. Briefly described, the cone tree provides a three-dimensional node-link structure with a hierarchical geometry within which the relative positions of nodes and links, as viewed from the primary viewing position in front of a computer monitor, can change without losing the perceived constancy of the structure as a whole. When a user selects a part of the structure, the selected part can be brought to a primary viewing position by changing the geometry of the structure without loss of object constancy.
FIG. 1 illustrates a three dimensional, horizontally oriented, hierarchical structure 60 displayed on a computer monitor. Structure 60 has conic substructures that can rotate while preserving object constancy. Structure 60 includes conic substructures 62, 64, 66, 68 and 70 in hierarchical levels. Several cues within structure 60 allow a human eye to perceive it as three-dimensional. For example, the bases or directories of the conic substructures, illustratively elliptical as can be seen from base 72 of conic substructure 62, are perceptible as tilted circles receding from the viewing point. Also, the links, illustratively of different lengths as can be seen from links 74 and 76, are perceptible as having equal length due to some links being closer to the viewing point than others. The nodes, illustratively including selectable units of different sizes as can be seen from nodes 78 and 80, are perceptible as of equal size dues to some nodes being closer to the viewing point than others.
An image of structure 60 on a computer monitor could be followed by a sequence of images in which each of the conic substructures is replaced by a series of similar conic substructures that are perceptible as slightly rotated continuations, rotating about horizontal axes. For example, if a user indicated node 82 and requested that it be moved to the primary viewing position closest to the viewer, conic substructures 70, 68, 66 and 62 could rotate to move node 82 to the requested position. Viewing structure 60 from above, the rotation to move node 82 to the primary viewing position could be as follows: Substructures 70, 68 and 66 could rotate counterclockwise. Substructure 62 could rotate clockwise. These rotations could be concurrent, and continue until links 84, 86, 88 and 90 are all aligned toward the primary viewing position.
The user can request that a node be moved to the primary viewing position by selecting that node's selectable unit. Node 100, in addition to including selectable unit for requesting that it be moved, includes selectable unit 102, called a grow tab. By selecting a grow tab the user requests presentation of the children nodes of the selected node, which are not displayed while the grow tab is displayed. This explains why node 96 does not include a grow tab in FIG. 1--children nodes 94 and 95 are already displayed.
For additional discussion of the cone tree and it implementation in a computer system refer to U.S. Pat. No. 5,295,243.
C. The WebBook
A book metaphor is used to browse a list of linked documents in U.S. Ser. No. 08/525,936 to Robertson et al. entitled "Display System for Displaying Lists of Linked Documents." Briefly described, an interactive interface, called the WebBook, presents a list of pages to a viewer of a computer monitor in a book metaphor, thus conveying a relationship between the different pages. Each page in the WebBook represents a page in the list of linked documents.
FIG. 2 illustrates the computer instructions 100 for generating and using the WebBook with a computer system. The first step 101 is to generate or otherwise obtain a list of Web Pages. This can be accomplished in various ways. One way is to analyze a page, such as a home page, and follow and download all the relative links on the home page. This is repeated for each subsequent page. Following relative links is useful since these pages will typically be closely related. Each page on a chain of relative links would then be included in the set of pages. Variations on this would limit the number of relative links traversed. This list of pages will be in the order that they would appear in the book.
Next, during step 102, page objects for each web page are generated. A page object is the internal representation of a web page for use in the book metaphor. Page objects and their contents are described in greater detail below. Next, during step 103 the WebBook is generated from the page objects. The WebBook has a basic structure which lists the pages and provides various controls. When a user opens the WebBook, during step 104 the WebBook rendered by the computer controlled display system and displayed on a display. The first time the book is opened, the cover will be displayed, or alternatively a first page (depending on whether the book has a cover). Subsequent instances of opening the book will cause it to be opened at the point where it was last closed. As will be described in detail below, only those pages corresponding to a particular page in a book are visible. Other page objects are marked as not displayed.
The user during step 105 then traverses the WebBook using page turning operations and marking interesting pages until through viewing or using the WebBook. The page turning operations are animated so as to give the user a sense of an actual page turning. When the user is done, the page in the WebBook last open is marked in the WebBook, step 106, and WebBook is closed, step 107. Optionally, during step 108 the WebBook may be stowed. Stowing the WebBook is equivalent of putting a book on a bookshelf.
WebBooks themselves may be organized as collections and stored as icons on a bookshelf. This would permit the storing of multiple WebBooks each having their own related subject. WebBooks may also be transferred and used by other users. Finally, pages may be added to a WebBook. This would require creation of a page object(s) for the added page(s) and regeneration of the WebBook.
FIG. 3 illustrates a WebBook as displayed on a display of a computer system. The WebBook 110 includes a first page 112 and a second page 113, each having an identical structure. The first page 112 is an instance of a left page and the second page 113 is an instance of a right page. Pages 112 and 113 each includes links 111 to other pages within the WebBook. As is typical, links 111 are indicated by underlined text. For example, clicking on link 111a opens the WebBook to a page containing a paper about cone tree visualization. Vertical scroll bars 114 and 115 provide for vertical scrolling on their respective pages. Horizontal scroll bars 116 and 117 provide for horizontal scrolling on their respective pages. Superimposed within the horizontal scroll bars are page references 132 and 133 which indicate the page number in the book for each page. Scaling bars 118 and 119 enable font scaling on the respective pages. Each of the pages also has a title bar 120 and 121 which is used to indicate the title of the respective page. The content and layout of the page is determined by the HTML macros defining the page.
Book control buttons are presented at the bottom edge of the WebBook 110. Close button 122 provides for closing the book. Back button 123 provides for looking at a prior page. History button 124 provides for reviewing the history of pages looked at. Mark button 125 provides for creating a bookmark for a page being viewed. Illustrated in FIG. 3, bookmark 130 indicates that page 14 has been marked. Help button 126 provides for invoking various help functions for the WebBook 110. The help functions are in the form of text describing how to perform particular functions in the WebBook. Options button 127 provides for specifying various operational parameters in the WebBook. An example is specifying the timing for flipping pages in the WebBook. Labeled "Scan &lt;", button 128 provides for automatic scanning of pages to the lower numbered pages. Labeled "Scan &gt;", button 129 provides for automatic scanning of pages to the higher numbered pages. Re-sizing boxes 131 may be used to re-size the WebBook 110 using a point and drag function.
Finally, book edge areas 132 and 133 are used to provide a visual indication of relative positioning within the book, e.g. the number of pages on that "side" of the book. The book edge areas 132 and 133 will change in size as the pages are traversed. Also, the book edge areas may be used as a means for directly accessing pages in the book (e.g. mimicking the activity of thumbing through the book in groups of pages). This is accomplished by a point and click operation pointing to the edge.
Referring to FIG. 4 when displayed with a cover, the contents of the WebBook is hidden. Display of a cover may be useful for security purposes, wherein a password or other security mechanism may be required before the book may be opened. Further, when displayed with a cover, the first page will be a left page in the WebBook because when opened two pages are displayed.
C.1. Generating a List of Pages
A list of pages for the WebBook can be obtained in any one of many ways. As mentioned above, one way is to gather all the relative links that originate from a particular home page. It has been determined through observation that the use of relative links is a common indicator of pages that are related. This is because the use of relative links makes a collection of pages easily transportable (e.g. to move the pages from one server to another). During this process of following the relative links, each page is retrieved and stored. In this technique the pages would be ordered so as to retain relationships. In other words, for a first relative link on a home page, all subsequent relative links are ordered sequentially. They would be followed by a second relative link on the home page followed by all its subsequent relative links. This ordering will allow related pages to be grouped sequentially within the WebBook. An exception is that relative links that are specified two or more times are represented in the list only once (e.g. typically the home page is specified on each page).
Other techniques for creating lists of pages may be used so long as they produce a list that is ordered in the way that the pages would appear in the WebBook.
C.2. WebBook
The WebBook is created from the list of page objects. The WebBook is merely a control structure for manipulating and controlling the page objects. The page objects are positioned in a 3-D space so that that they are co-planer.
The WebBook data structure is dynamic and changes as the book is changed. Preferably, object oriented programming techniques are used to realize the WebBook. So the data structure represents a WebBook object in that context. In any event, the data structure is comprised of a graphical control portion, a list of page objects and WebBook status information. The graphical control portion contains various information for controlling interactive graphical objects. Such information includes transient properties for animation control, 3-D rendering information and a list of "children" objects. The children objects are graphical objects that are manipulated when the WebBook is manipulated. Such objects would include page objects and the graphical objects representing the control buttons and page markers. The list of page objects is merely a page sequence reference to the page objects. The WebBook status information contains various information about the state of the WebBook at a point in time.
The information contained in the objects further specify software routines which utilize the information contained in the object to actually perform the desired function.
C.3. Page Object
FIG. 5 illustrates a page object, a left page object specifically, from a spatial perspective. This figure shows a page object as a plane 141 in 3-D space with respect to axes 144. The plane 141 represents the actual "page" of information on which content is displayed. The plane 141 has associated with it content 142 and an axis of rotation 143 along the right edge (from the viewers perspective). The axis of rotation 143 indicates where the page will be turned (i.e. the spine of the WebBook). The content 142 is the HTML formatted text and image information for the page. FIG. 6 illustrates a right page object. Plane 151 has associated with it content 152. The significant difference is that the axis of rotation 153 is on the left edge of the plane (from the viewers perspective). So when the page turns, it will occur in the opposite orientation then for a left page. For each page object, the content is rendered onto the plane. Generally, the plane is the size of the book (which can be re-sized by the user), so the user will scroll through the content.
A visually appealing aspect of the WebBook is the turning of pages, which is animated. This provides the user with a visual effect approximating the physical activity of turning a page in a book. Generally, the sequence of steps is to rotate the page to be turned about the axis of rotation, rotate the page on the other side of the page to be turned about the axis of rotation, at a point orthogonal to the viewer turn off the page to be turned and turn on the page on the other side, turn off the page being covered, and turn on the new page being revealed by the page turn.
Page "turning" may be accomplished in various ways. One is through a point and click operation on a page or page edge using a cursor control device. In the currently preferred embodiment, pointing and clicking on the left page (or left page edge) will cause the next lower pair of pages to be turned to. Conversely, point and clicking on the right page (or right page edge) will cause the next higher pair of pages to be turned to. Of course other means of interacting with the page, e.g. the use of gestures such as drag cursor left or drag cursor right could be used to implement page turning in the corresponding direction. Page turning may also occur through use of the scan operation provided with the WebBook. The scan operation will cause the pages to turn at a predetermined rate.
FIGS. 7 and 8 illustrate the steps in a page turn. Referring to FIG. 7, a page turn operation of page 113 of FIG. 3 has been initiated. Although not illustrated a first step in accomplishing a visually pleasing page turn is to offset page 113 with the page being revealed. It has been determined that during a page turn, if the pages become co-planer, the content of the page being turned becomes jumbled. This is because the page being revealed two pages hence or before has content that is also being revealed. In any event, as page 113 rotates along an axis 162 corresponding to the spine of a book, page 161 is being revealed. Note that page 113 remains in a rigid plane as it turns. As noted above, the user may modify the speed at which this turn occurs. Referring to FIG. 8, at a point in the rotation of page 113 its "other side", page 163 becomes visible. Page 161 also appears. At predetermined points during the page turn, the content of pages 112 and 113 are turned off indicating that the page is turned. Although not illustrated, the rotation of pages continues until pages 161 and 163 are revealed, completing the page turn animation.
During a page turn, two page objects rotate. Conceptually, left and right pages are positioned back to back. So a page turn involves rotating each in unison to simulate the actual turning of a page.
The animation sequence for turning pages or ruffling pages is generally the same. Ruffling can be thought of as multiple concurrent page turns. FIG. 9 illustrates a step in the ruffling through the pages of a WebBook, during which a plurality of pages are being turned concurrently. A difference in ruffling is that intermediate pages are never fully visible to the user since it is quickly being overlaid by a next page. Ruffling in the currently preferred embodiment is invoked by pointing to a page and holding down the button on the cursor control device for at least a predetermined time. When the button associated with the cursor control device is released, the ruffling will stop.